package com.yangzhe.algorithm.c038;

import java.util.HashSet;

// 字符串的全部子序列
// 子序列本身是可以有重复的，只是这个题目要求去重
// 测试链接 : https://www.nowcoder.com/practice/92e6247998294f2c933906fdedbc6e6a
public class Code01_Subsequences {
    public static void main(String[] args) {
        String[] s1 = generatePermutation1("abba");
        String[] s2 = generatePermutation2("abba");

        System.out.println("-------方法1------------");
        print(s1);
        System.out.println("-------方法2------------");
        print(s2);
    }

    private static void print(String[] s2) {
        for (int i = 0; i < s2.length; i++) {
            String s = s2[i];
            System.out.print("\"" + s + "\",");
        }
        System.out.println();
    }

    /**
     * 思路：递归
     * 1. 将字符串转为数组，用索引i代表当前位置
     * 2. 每个i位置都可以选择和不选，选择就将字符缓存到path中
     * 3. 继续向下递归，到底之后，将path放在hashset中去重
     * <p>
     * 按左神的做法 abba，会返回abb和bba、ab和ba都算重复的，其实有问题
     *
     * @param str
     * @return
     */
    public static String[] generatePermutation1(String str) {
        char[] s = str.toCharArray();

        HashSet<String> set = new HashSet<>();
        f1(s, 0, new StringBuilder(), set);

        String[] result = new String[set.size()];

        int i = 0;
        for (String next : set) {
            result[i++] = next;
        }

        return result;
    }

    /**
     * @param s    字符数组
     * @param i    当前递归位置
     * @param path 缓存路径
     * @param set  用于去重
     */
    public static void f1(char[] s, int i, StringBuilder path, HashSet<String> set) {
        // 如果遍历到底了
        if (i == s.length) {
            set.add(path.toString());
        } else {
            path.append(s[i]);
            f1(s, i + 1, path, set);
            path.deleteCharAt(path.length() - 1);
            f1(s, i + 1, path, set);
        }
    }

    public static String[] generatePermutation2(String str) {
        char[] s = str.toCharArray();

        HashSet<String> set = new HashSet<>();
        f2(s, 0, new char[s.length], 0, set);

        String[] result = new String[set.size()];

        int i = 0;
        for (String next : set) {
            result[i++] = next;
        }

        return result;
    }

    /**
     * 复用path
     *
     * @param s    字符串数组
     * @param i    当前递归位置
     * @param path 缓存路径
     * @param size path长度
     * @param set  用于去重
     */
    public static void f2(char[] s, int i, char[] path, int size, HashSet<String> set) {
        if (i == s.length) {
            set.add(String.copyValueOf(path, 0, size));
        } else {
            path[size] = s[i];
            f2(s, i + 1, path, size + 1, set);
            f2(s, i + 1, path, size, set);
        }
    }
}